#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution
{
public:
    int maxTotalReward(vector<int> &rewardValues)
    {
        sort(rewardValues.begin(), rewardValues.end());
        return subProblem(rewardValues, rewardValues.size() - 1, INT_MAX);
    }

    //  计算[0,index],满足小于k的最大值
    int subProblem(vector<int> &rewardValues, int index, int k)
    {
        if (index < 0 || k <= 0)
            return -1;
        if (index == 0)
            if (rewardValues[0] < k)
                return rewardValues[0];
            else
                return 0;
        int sol1 = subProblem(rewardValues, index - 1, min(k - rewardValues[index], rewardValues[index]));
        int sol2 = subProblem(rewardValues, index - 1, k);
        if (sol1 >= 0 && sol2 >= 0)
            return max(sol1 + rewardValues[index], sol2);
        else if (sol1 >= 0)
            return sol1 + rewardValues[index];
        else if (sol2 >= 0)
            return sol2;
        else
            return -1;
    }
};

int main()
{
    cout << "Code3180" << endl;
    Solution s;
    // vector<int> rewardValues = {1, 1, 3, 3};
    vector<int> rewardValues = {1, 5, 4};
    cout << s.maxTotalReward(rewardValues) << endl;
    return 0;
}